#include <ctime>
#include <cstdlib>
#include <iostream>
#include "linklist_mergesort.h"

Node* build_random_list(int size) {
	Node* first = NULL;
	srand(time(NULL));
	for ( int i = 0; i < size; i++) {
		Node * n = new Node;
		n->next = first;
		n->value = rand()%1000;
		first = n;
	}
	Node* head = new Node;
	head->next = first;
	head->value = size;
	return head;
}

//advance n in size steps if n has size steps; otherwise, advance as much as possible 
int advance(Node* &n, int size) {
	int i = 0;
	while ( n != NULL && i < size) {
		n = n->next;
		i++;
	}
	return i;
}

void merge(Node *p, Node *q, int size, Node *prev, Node *next) {
	int i,j;
	for(i = 0, j = 0; i < size && j < size && p != NULL && q != NULL; ) {
		if (p->value <= q->value) {
			prev->next = p; prev = p;
			p = p->next; i++;
		}
		else {
			prev->next = q; prev = q;
			q = q->next; j++;
		}
	}
	if (i < size && p != nullptr) { //p remains
		prev->next = p;
		advance(p,size-i-1);
		if (p != nullptr) p->next = next;
	}
	else { //q  remains
		prev->next = q; // no need to adjust the next pointer of the last node of list q
	}
	
}
void mergesort(Node * head, int length) {
	Node *p, *q, *prev, *next;
	for (int size = 1; size < length; size *= 2) {
		prev = head;
		p = q = next = head->next;
		while ( p != nullptr ) {
			advance(q,size);
			advance(next,2*size);
			merge(p,q,size,prev,next);
			advance(prev,2*size); p = next; q = p;
		}
	}
}

void print_list(Node* head) {
	if (head == nullptr) return;
	std::cout << "the list contains " << head->value << " nodes :";
	head = head->next;
	while(head != nullptr) {
		std::cout << ' ' << head->value;
		head = head->next;
	}
	std::cout << std::endl;
}